#include <bits/stdc++.h>
using namespace std;

// 【题目】496. 下一个更大元素 I
// 【难度】简单
// 【提交】2025.9.25 https://leetcode.cn/problems/next-greater-element-i/submissions/665366801
// 【标签】单调栈 哈希表
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> hashmap;
        stack<int> DecStack;

        for(int i = nums2.size() - 1; i >= 0; i--){
            int TempNum = nums2[i];
            while(!DecStack.empty() && TempNum >= DecStack.top()){
                DecStack.pop();
            }
            hashmap[TempNum] = DecStack.empty() ? -1 : DecStack.top();
            DecStack.push(TempNum);
        }
        vector<int> result(nums1.size());
        for(int i = 0; i < nums1.size(); ++i){
            result[i] = hashmap[nums1[i]];
        }
        return result;
    }
};

/**
 * @brief 学习总结：
 * 用到了map,重新学习了一遍哈希表的知识，也熟悉了一下map的一些相关语法，结合LC1944那题，知道了单调栈的使用场景  
*/


/*
--------------------------------------------------------------------------------------------------------------
（（学习笔记：LeetCode 496「下一个更大元素 I」
（提交记录：2024-03-25，C++，用时 20 ms，内存 7.8 MB）

一、题意与模型
给定两个数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。要求返回一个数组 result，其中 result[i] 表示 nums1[i] 在 nums2 中的下一个更大元素。如果不存在下一个更大元素，则返回 -1。

二、标准 DP 状态设计
设 nextGreater[i] 表示 nums2[i] 的下一个更大元素。我们可以利用栈来维护 nums2 数组中的递减序列，从而找到每个元素的下一个更大元素。
初始化：栈为空，hashmap 用来记录每个数的下一个更大元素。
转移：从 nums2 的尾部开始遍历，每遇到一个元素，栈中比它小的元素会被弹出，并更新其下一个更大元素。
最终：通过 hashmap 查找 nums1[i] 对应的下一个更大元素。

三、你的实现思路
使用单调栈的思想，从 nums2 的末尾开始遍历，维护栈中的元素按递减顺序排列。对于每个元素，如果栈顶元素小于当前元素，则弹出栈顶元素，因为当前元素就是它的下一个更大元素。
遍历完 nums2 后，使用 hashmap 查找 nums1[i] 的下一个更大元素。

四、逐行注释（带细节提醒）
cpp
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> hashmap; // 用哈希表记录 nums2 中每个元素的下一个更大元素
stack<int> DecStack; // 用栈维护递减顺序的元素

arduino
    // 从 nums2 的尾部开始遍历
    for (int i = nums2.size() - 1; i >= 0; i--) {
        int TempNum = nums2[i];  // 当前遍历的元素

        // 弹出栈中所有小于等于当前元素的元素
        while (!DecStack.empty() && TempNum >= DecStack.top()) {
            DecStack.pop();   // 弹出栈顶元素
        }

        // 如果栈为空，说明没有更大的元素，否则栈顶元素是下一个更大的元素
        hashmap[TempNum] = DecStack.empty() ? -1 : DecStack.top();

        // 将当前元素压入栈中
        DecStack.push(TempNum);
    }

    // 根据 nums1 中的元素返回对应的下一个更大元素
    vector<int> result(nums1.size());
    for (int i = 0; i < nums1.size(); ++i) {
        result[i] = hashmap[nums1[i]];  // 查找 nums1 中每个元素的下一个更大元素
    }

    return result;  // 返回结果数组
}
};

五、正确性证明
在 nums2 中我们从右到左遍历，确保栈中的元素始终保持递减顺序。
每次遍历时，当前元素要么没有更大的元素（栈为空），要么栈顶的元素就是下一个更大的元素。由于每个元素在栈中最多入栈和出栈一次，因此该算法是正确的。

六、复杂度
时间：O(n + m)，其中 n 是 nums2 的长度，m 是 nums1 的长度。遍历 nums2 和 nums1 分别各占 O(n) 和 O(m)，每个元素最多进栈和出栈一次，因此时间复杂度是 O(n)。
空间：O(n)，栈和哈希表分别存储最多 nums2 中的 n 个元素。

七、优缺点分析
优点：
利用单调栈保证了在 O(n) 时间内计算每个元素的下一个更大元素，算法高效。
代码简洁，符合单调栈的应用模式。

缺点：
代码的栈操作较为复杂，理解上需要一些时间。
如果 nums1 和 nums2 很大，可能需要额外优化空间复杂度（比如在哈希表的使用上）。

八、改进建议
栈的使用是最优选择，空间复杂度可以优化到 O(n)，不需要进一步改进。
可以考虑直接利用 unordered_map 查找结果，而不需要额外遍历 nums1。

九、一句话总结
该题目利用单调栈高效地解决了下一个更大元素问题，时间复杂度为 O(n)，空间复杂度为 O(n)，实现简单，适合大规模数据的处理。
--------------------------------------------------------------------------------------------------------------
*/